import java.util.*;

public class project {
    public int numDistinct(String s, String t) {
        if(s.length()<t.length()){
            return 0;
        }
        int row=s.length();
        int col=t.length();
        int[][] dp=new int[row+1][col+1];
        for(int i=0;i<=row;i++){
            dp[i][col]=1;
        }
        for(int i=row-1;i>=0;i--){
            for(int j=col-1;j>=0;j--){
                char chS=s.charAt(i);
                char chT=t.charAt(j);
                if(chS==chT){
                    dp[i][j]=dp[i+1][j]+dp[i+1][j+1];
                }else{
                    dp[i][j]=dp[i+1][j];
                }
            }
        }
        return dp[0][0];
    }



















    public int numDistinct1(String s, String t) {
        if(s.length()<t.length()){
            return 0;
        }
        int row=s.length();
        int col=t.length();
        int[][] dp=new int[row+1][col+1];
        for(int i=0;i<row;i++){
            dp[i][col]=1;
        }
        for(int i=row-1;i>=0;i--){
            char chS=s.charAt(i);
            for(int j=col-1;j>=0;j--){
                char chT=t.charAt(j);
                if(chS==chT){
                    dp[i][j]=dp[i+1][j+1]+dp[i+1][j];
                }else{
                    dp[i][j]=dp[i+1][j];
                }
            }
        }
        return dp[0][0];
    }





















    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> list=new ArrayList<>();
        int[] arr=new int[numCourses];
        int[] ret=new int[numCourses];
        int index=0;
        for(int i=0;i<numCourses;i++){
            list.add(new ArrayList<>());
        }
        for(int[] pre:prerequisites){
            list.get(pre[1]).add(pre[0]);
            arr[pre[0]]++;
        }
        Queue<Integer> queue=new ArrayDeque<>();
        for(int i=0;i<numCourses;i++){
            if(arr[i]==0){
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()){
            int value=queue.poll();
            ret[index++]=value;
            for(int l:list.get(value)){
                arr[l]--;
                if(arr[l]==0){
                    queue.offer(l);
                }
            }
        }
        return index==numCourses?ret:new int[0];
    }
















    public int[] findOrder1(int numCourses, int[][] prerequisites) {
        List<List<Integer>> list=new ArrayList<>();
        int[] arr=new int[numCourses];
        int[] ret=new int[numCourses];
        int index=0;
        for(int i=0;i<numCourses;i++){
            list.add(new ArrayList<>());
        }
        for(int[] prerequisite:prerequisites){
            list.get(prerequisite[1]).add(prerequisite[0]);
            arr[prerequisite[0]]++;
        }
        Queue<Integer> queue=new ArrayDeque<>();
        for(int i=0;i<numCourses;i++){
            if(arr[i]==0){
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()){
            int value=queue.poll();
            ret[index++]=value;
            for(int l:list.get(value)){
                arr[l]--;
                if(arr[l]==0){
                    queue.add(l);
                }
            }
        }
        return index==numCourses?ret:new int[0];
    }














    int[] subtraction(int[] a, int[] b) { // 向量相减
        return new int[]{a[0] - b[0], a[1] - b[1]};
    }
    double cross(int[] a, int[] b) { // 叉乘
        return a[0] * b[1] - a[1] * b[0];
    }
    double getArea(int[] a, int[] b, int[] c) { // 向量 ab 转为 向量 ac 过程中扫过的面积
        return cross(subtraction(b, a), subtraction(c, a));
    }
    public int[][] outerTrees(int[][] trees) {
        Arrays.sort(trees, (a, b)->{
            return a[0] != b[0] ? a[0] - b[0] : a[1] - b[1];
        });
        int n = trees.length, tp = 0;
        int[] stk = new int[n + 10];
        boolean[] vis = new boolean[n + 10];
        stk[++tp] = 0; // 不标记起点
        for (int i = 1; i < n; i++) {
            int[] c = trees[i];
            while (tp >= 2) {
                int[] a = trees[stk[tp - 1]], b = trees[stk[tp]];
                if (getArea(a, b, c) < 0) vis[stk[tp--]] = false;
                else break;
            }
            stk[++tp] = i;
            vis[i] = true;
        }
        int size = tp;
        for (int i = n - 1; i >= 0; i--) {
            if (vis[i]) continue;
            int[] c = trees[i];
            while (tp > size) {
                int[] a = trees[stk[tp - 1]], b = trees[stk[tp]];
                if (getArea(a, b, c) < 0) {
                    // vis[stk[tp--]] = false; // 非必须
                    tp--;
                }
                else break;
            }
            stk[++tp] = i;
            // vis[i] = true; // 非必须
        }
        int[][] ans = new int[tp - 1][2];
        for (int i = 1; i < tp; i++) ans[i - 1] = trees[stk[i]];
        return ans;
    }
}
